package org.hw.algorithm.recursion;

/**
 * @Program: demo
 * @Author: hewei
 * @Date: 2024-03-27 17:53
 * @Description:
 * 八皇后递归回溯求解：二数组实现
 **/
import java.util.ArrayList;
import java.util.List;

public class EightQueens {
    static int N = 8; // 棋盘大小
    // 假设有一个全局变量board，初始化为N×N的二维数组模拟棋盘，用于存储皇后的位置
    static int[][] board = new int[N][N];
    /*解决方案列表*/
    static List<List<String>> solutions = new ArrayList<>();

    public static void main(String[] args) {
        solveNQueens(0);
        System.out.println("放置方案数量："+solutions.size());
        printSolutions();
    }

     /**
      * 解决N皇后问题的核心回溯函数
      *
      *     1、首先第一行第一列可以放置，递归压栈至第二行
      *     2、遍历放置第二行的所有列：从第一列开始遍历，找到可以放置的位置，同时压栈至第三行
      *     3、依次类推，直到第 N 行（row==N），一个解决方案完成，当次递归结束返回，开始回溯
      *     4、回溯至没有遍历完所有列的最近的行，开始接着递归剩下的列
      *     5、依次类推，直至所有行的所有列都遍历完毕，就找到了所有的解决方案
      * */
    public static void solveNQueens(int row) {
        if (row == N) { // 如果已经把N个皇后都放好了
            addSolution();
            return;
        }

        for (int col = 0; col < N; col++) { // 尝试当前行的所有列
            if (isSafe(row, col)) { // 如果当前位置可以放置皇后
                placeQueen(row, col); // 放置皇后
                solveNQueens(row + 1); // 继续解决下一行
                removeQueen(row, col); // 回溯，移除当前皇后
            }
        }
    }

    // 检查在给定位置放置皇后是否安全（即不与已放置的皇后冲突）
    private static boolean isSafe(int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++)
            if (board[i][col] == 1)
                return false;

        // 检查左上方对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 1)
                return false;

        // 检查右上方对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++)
            if (board[i][j] == 1)
                return false;

        return true;
    }

    // 在棋盘上放置皇后
    private static void placeQueen(int row, int col) {
        board[row][col] = 1;
    }

    // 移除棋盘上的皇后
    private static void removeQueen(int row, int col) {
        board[row][col] = 0;
    }

    // 保存解决方案
    private static void addSolution() {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 1)
                    sb.append("Q ");
                else
                    sb.append(". ");
            }
            solution.add(sb.toString().trim());
        }
        solutions.add(solution);
    }

    // 打印所有解决方案
    private static void printSolutions() {
        for (List<String> sol : solutions) {
            for (String line : sol) {
                System.out.println(line);
            }
            System.out.println("-----------------------------"); // 分隔不同的解决方案
        }
    }

}